package com.leetcode.array;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

/**
 * @author: ZhouBert
 * @date: 2019/9/26
 * @description: 41. 缺失的第一个正数
 * [困难]
 * <p>
 * 给定一个[未排序]的整数数组，找出其中没有出现的最小的正整数。
 * <p>
 * 示例 1:
 * 输入: [1,2,0]
 * 输出: 3
 * <p>
 * 示例 2:
 * 输入: [3,4,-1,1]
 * 输出: 2
 * <p>
 * 示例 3:
 * 输入: [7,8,9,11,12]
 * 输出: 1
 * 说明:
 * <p>
 * 你的算法的时间复杂度应为O(n)，并且只能使用常数级别的空间。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/first-missing-positive
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class FirstMissingPositive41 {

	/**
	 * 如果n也算常数级别，但是	Arrays.sort	的时间复杂度已经是 O(nlogn) 了
	 *
	 * @param nums
	 * @return
	 */
	public static int firstMissingPositive_out(int[] nums) {
		///1.排序
		Arrays.sort(nums);
		int countNotPositive = 0;
		///2.去重
		for (int i = 0; i < nums.length; i++) {
			if (nums[i] < 1 || (i > 0 && nums[i] == nums[i - 1])) {
				countNotPositive++;
				continue;
			}
			if (nums[i] > i - countNotPositive + 1) {
				return i - countNotPositive + 1;
			}
		}
		return nums.length - countNotPositive + 1;
	}

	/**
	 * TODO:将各种数据结构结合起来！
	 * 你的算法的时间复杂度应为O(n)，并且只能使用常数级别的空间。
	 * todo:hash 计数。这个方法也不符合题意
	 * 思路：检索--》O(1)级别的检索--》hash
	 *
	 * @param nums
	 * @return
	 */
	public static int firstMissingPositive_out2(int[] nums) {
		if (nums == null || nums.length == 0) {
			return 1;
		}
		Set<Integer> set = new HashSet<>();
		///1.当 set 没有
		for (int i = 0; i < nums.length; i++) {
			if (nums[i] > 0) {
				set.add(nums[i]);
			}
		}

		for (int i = 1; i <= set.size(); i++) {
			if (!set.contains(i)) {
				return i;
			}
		}
		return set.size() + 1;
	}

	/**
	 * TODO:利用数组的特性！
	 * todo:思路 * 遍历一次数组把大于等于1的和小于数组大小的值放到原数组对应位置，然后再遍历一次数组查当前下标是否和值对应，如果不对应那这个下标就是答案，否则遍历完都没出现那么答案就是数组长度加1。
	 *
	 * @param nums
	 * @return
	 */
	public static int firstMissingPositive(int[] nums) {
		if (nums == null || nums.length == 0) {
			return 1;
		}
		int temp = 0;
		///1.理想数组[1,2,3,...]
		for (int i = 0; i < nums.length; i++) {
			///如果超出两端的范围，扔掉；如果位置理想，不用替换
			if (nums[i] < 1 || nums[i] > nums.length || nums[i] - 1 == i) {

			} else {
				//暂时存储下一个交换位置的值
				temp = nums[nums[i] - 1];
				///完成第一次替换
				nums[nums[i] - 1] = nums[i];
				putValue(nums, i, temp);
				///todo:没必要处理原来的位置，处理了反而会错！
				//nums[i] = 0;
			}
//			if (nums[i] - 1 != i) {
//
//			}

		}
		///2.根据空缺判断第一个正数
		for (int i = 0; i < nums.length; i++) {
			if (nums[i] != (i + 1)) {
				return i + 1;
			}
		}
		return nums.length+1;
	}

	/**
	 * 处理下一个的值
	 * @param nums
	 * @param index
	 * @param temp
	 */
	public static void putValue(int[] nums, int index, int temp) {
//		int idealLoc=temp-1;
//		///当位置索引大于当前索引的时候才需要处理
//		if (idealLoc>index){
//
//		}
		int itemp=0;
		if (temp < 1 || temp > nums.length ){

		}else{
			//暂时存储下一个交换位置的值
			itemp = nums[temp- 1];
			///nums[i] = 0;
			///完成第一次替换
			nums[temp- 1] = temp;
			if (temp==itemp){
				return;
			}
			putValue(nums, temp- 1, itemp);
		}
	}

	public static void main(String[] args) {
		int[] ints = new int[]{1, 2, 0};
		//ints=new int[]{2};
		ints = new int[]{3, 4, -1, 1};
		ints = new int[]{1, 1};
		ints = new int[]{1};
		ints = new int[]{2,1};
		///System.out.println(firstMissingPositive_out(ints));
		///System.out.println(firstMissingPositive_out2(ints));
		System.out.println(firstMissingPositive(ints));
	}
}
